We study streaming principal component analysis (PCA), that is to find, in$O(dk)$ space, the top $k$ eigenvectors of a $d\times d$ hidden matrix $\bf\Sigma$ with online vectors drawn from covariance matrix $\bf \Sigma$. We provide $\textit{global}$ convergence for Oja's algorithm which ispopularly used in practice but lacks theoretical understanding for $k>1$. Wealso provide a modified variant $\mathsf{Oja}^{++}$ that runs $\textit{evenfaster}$ than Oja's. Our results match the information theoretic lower bound interms of dependency on error, on eigengap, on rank $k$, and on dimension $d$,up to poly-log factors. In addition, our convergence rate can be made gap-free,that is proportional to the approximation error and independent of theeigengap. In contrast, for general rank $k$, before our work (1) it was open to designany algorithm with efficient global convergence rate; and (2) it was open todesign any algorithm with (even local) gap-free convergence rate in $O(dk)$space.
展开▼
机译：我们研究流式主成分分析（PCA），即在$ O（dk）$空间中找到绘制了在线矢量的$ d \ times d $隐藏矩阵$ \ bf \ Sigma $的顶部$ k $特征向量来自协方差矩阵$ \ bf \ Sigma $。我们为Oja算法提供$ \ textit {global} $收敛性，该算法在实践中广为使用，但对$ k> 1 $缺乏理论上的理解。我们还提供了一个经过修改的变体$ \ mathsf {Oja} ^ {++} $，该变体比Oja的运行$ \ textit {evenfaster} $。我们的结果与错误，eigengap，等级$ k $和维度$ d $的信息理论下界相吻合，直到多元对数因子为止。另外，可以使我们的收敛速度无间隙，它与近似误差成比例，并且与eengengap无关。相比之下，对于一般排名$ k $，在我们进行工作之前（1），可以设计出具有高效全局收敛速度的任何算法； （2）设计在（O（dk））空间中具有（甚至局部）无间隙收敛速率的任何算法都是开放的。
展开▼
